/**
 * The arithmetic sequence, 1487, 4817, 8147, in which each of the terms 
 * increases by 3330, is unusual in two ways: (i) each of the three terms 
 * are prime, and, (ii) each of the 4-digit numbers are permutations of 
 * one another.
 *
 * There are no arithmetic sequences made up of three 1-, 2-, or 3-digit 
 * primes, exhibiting this property, but there is one other 4-digit 
 * increasing sequence.
 *
 * What 12-digit number do you form by concatenating the three terms in 
 * this sequence?
 *
 * ANSWER: 296962999629
 */

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include "prime.h"

static int sort_digits(int n)
{
	int digits[100];
	int count = 0;
	while (n > 0)
	{
		digits[count++] = n % 10;
		n /= 10;
	}

	std::sort(digits + 0, digits + count);
	n = 0;
	while (count > 0)
	{
		n = n * 10 + digits[--count];
	}
	return n;
}

static void search_triple(
	std::vector<std::pair<int,int>>::const_iterator begin, 
	std::vector<std::pair<int,int>>::const_iterator end)
{
	for (auto it1 = begin; it1 != end; ++it1)
	{
		for (auto it2 = it1; ++it2 != end; )
		{
			for (auto it3 = it2; ++it3 != end; )
			{
				if (it2->second*2 == it1->second+it3->second)
				{
					if (!(it1->second == 1487 && it2->second == 4817 && it3->second == 8147))
						std::cout << it1->second << it2->second << it3->second << std::endl;
				}
			}
		}
	}
}

void solve_problem_49()
{
	// Find all four-digit primes.
	prime_numbers primes(10000);

	// Map each four-digit prime to it's canonical presentation.
	std::vector<std::pair<int, int>> map; // canonical -> number
	for (auto it = primes.cbegin(); it != primes.cend(); ++it)
	{
		int p = *it;
		if (p >= 1000)
			map.push_back(std::pair<int,int>(sort_digits(p), p));
	}

	// Sort the map
	std::sort(map.begin(), map.end());

	// Find increasing sequence
	for (auto it = map.cbegin(); it != map.cend(); )
	{
		auto it2 = it + 1;
		while (it2 != map.cend() && it2->first == it->first)
			++it2;

		search_triple(it, it2);
		it = it2;
	}
}

